package org.czl.tree;

import java.util.Arrays;

public class l1584 {
    public static void main(String[] args) {
        minCostConnectPoints(new int[][]{{3,10},{5,2},{7,0}});
    }
    static int[] father;
    public static int minCostConnectPoints(int[][] points) {
        int[][] dis = new int[1000001][3];
        int c = 0;
        int n = points.length;
        int index = 0;
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                int x1 = points[i][0], y1 = points[i][1];
                int x2 = points[j][0], y2 = points[j][1];
                dis[index][2] = Math.abs(x1 - x2) + Math.abs(y1 - y2);
                dis[index][0] = i;
                dis[index++][1] = j;//表示这条边是i到j
            }
        }
        Arrays.sort(dis,0,index, (a, b) -> a[2] - b[2]);
        father = new int[n];
        for(int i = 0; i < n; i++){
            father[i] = i;
        }
        int ans = 0;
        for(int i = 0; i < c; i++){
            int[] arr = dis[i];
            int x = arr[0];
            int y = arr[1];
            if(union(x, y)){
                ans += arr[2];
            }
        }
        return ans;

    }
    //找出x的代表节点
    static int find(int x){
        if(x != father[x]){
            father[x] = find(father[x]);
        }
        return father[x];
    }

    static boolean union(int x, int y){
        int fx = find(x);
        int fy = find(y);
        if(fx != fy){
            father[fx] = fy;
            return true;
        }else{
            return false;
        }
    }
}
